package Wust_Java_Club_Middle_Test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//优化原理:
//一个位置的主对角线 ↙↗ 的横纵坐标之和相同
//一个位置的次对角线 ↖↘ 的横纵坐标之差相同
public class Eight_Queens_Puzzle01 {
	public static boolean[] top;
	public static boolean[] lefttop;
	public static boolean[] righttop;
	public static int[] ans;
	public static int count=0,n;
	
	public static boolean judge(int row,int col) {
		if(top[col]) return false;
		if(lefttop[row-col+n]) return false;
		if(righttop[row+col]) return false;
		return true;
	}
	
	public static void dfs(int row) {
		if(row>n) {
			++count;
			if(count<=3) {
				for(int i =1;i<=n;i++) System.out.print(ans[i]+" ");
				System.out.println();
			}
			return ;
		}
		
		for(int i=1;i<=n;i++) {
			if(judge(row, i)) {
				ans[row]=i;
				top[i]=true;
				lefttop[row-i+n] = true;
				righttop[row+i] = true;
				dfs(row+1);
				top[i]=false;
				lefttop[row-i+n] = false;
				righttop[row+i] = false;
			}
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(in.readLine());
		top = new boolean[n+1];
		lefttop = new boolean[2*n+1];
		righttop = new boolean[2*n+1];
		ans=new int[n+1];
		dfs(1);
		System.out.println(count);
	}
}
